#include "iostream"
#include "queue"
using namespace std;

const int MaxN = 100010, MaxM = 500010;// define MaxN & MaxM
struct edge{
	int to,dis,next;// define the toward ,distance , next point 
}; 
edge e[MaxM];// define edge array
int head[MaxN],dis[MaxN],cnt;// define for head array & distance arry & count
bool vis[MaxN];// define visited array
int n, m , s;

inline void add_edge(int u ,int v ,int d){
	cnt ++;
	e[cnt].dis = d;
	e[cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}
struct node{
	int dis;
	int pos;
	bool operator > (const node &x)const{
		return x.dis < dis;
	}
};
priority_queue<node> q;
inline void dijkstra(){
	dis[s] = 0;
	q.push((node){0,s});
	while(!q.empty()){
		//TODO
		node tmp = q.top();
		q.pop();
		int x = tmp.pos,d = tmp.dis;
		if(vis[x]){
			//TODO
			continue;
		}
		for(int i=head[x];i;i = e[i].next){
			//TODO
			int y = e[i].to;
			if(dis[y] > dis[x] + e[i].dis){
				//TODO
				dis[y] = dis[x] + e[i].dis;
				if(!vis[y]){
					//TODO
					q.push((node){dis[y],y});
				}
			}
		}
	}
}
int main (){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	
	
	
	return 0;
}
